#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 题目：判断一个链表是否有环，有就返回True，没有就返回False
# 解题思路一：快慢指针，快指针每次走两步，慢指针每次走一步，如果链表有环，则快慢指针就会相遇，否则，就是无环
class Solution:
    def hasCycle1(self , head):
        if head is None:
            return False
        fast, slow = head, head
        while (fast != None and fast.next != None):
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False


# 思路二：利用 set （集合）是一个不重复的序列，遍历列表，如果存在之前遍历过的节点，就说明链表有环
    def hasCycle2(self, head):
        if not head:
            return False
        dic = set()
        while head:
            if head in dic:
                return True
            dic.add(head)
            head = head.next
        return False
